⟸ Go Back ⟸

Exercise 10 (Homework 2).

(regular languages, decidable properties)

DFAs – some decidable properties

Show that the following computational problems are decidable by providing an algorithm (with reasonable cost) that solves them.

1. Given a DFA A, is L(A)=\emptyset?
2. Given a DFA A, is L(A) an infinite set?
3. Given two DFAs A and B, is L(A)=L(B)?
4. Given two DFAs A and B, is L(A)\subseteq L(B)?